package liangzhi;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @auther zhouliangliang
 * @date 2025/5/8 21:59
 * @description
 */
public class Tree<E> {

    /**
     * 构建
     * @param level
     * @return
     */
    public Node<E> genFullBinaryTree(int level) {
        if( level<=0 ) {
            return null;
        }
        Node<E> root = new Node<>(null);
        if(level == 1) {
            return root;
        }

        int currentLevel = 1;
        int nodeInCurLevel = 1;
        int nodeInNextLevel = 0;
        Queue<Node<E>> queue = new ArrayDeque<>();
        queue.add(root);

        while (currentLevel < level || !queue.isEmpty()) {
            Node<E> node = queue.poll();
            nodeInCurLevel--;

            Node<E> left = new Node<>(null);
            queue.add(left);
            node.setLeft(left);
            left.parent = node;
            nodeInNextLevel++;


            Node<E> right = new Node<>(null);
            queue.add(right);
            node.setRight(right);
            right.parent = node;
            nodeInNextLevel++;

            if(nodeInCurLevel == 0) {
                nodeInCurLevel = nodeInNextLevel;
                nodeInNextLevel = 0;
                currentLevel++;
            }
        }
        return root;
    }

    private static class Node<E> {
        private E data;
        private Node<E> left;
        private Node<E> right;
        private Node<E> parent;

        Node(E data) {
            this.data = data;
            this.left = null;
            this.right = null;
            this.parent = null;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

        public void setLeft(Node<E> left) {
            if( this.left != null) {
                this.left.parent = null;
            }

            this.left = left;

            if(left != null) {
                left.setParent(this);
            }
        }

        public void setRight(Node<E> right) {
            if(this.right != null) {
                this.right.parent = null;
            }
            this.right = right;
            if(right != null) {
                right.setParent(this);
            }
        }
    }
}

